#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/**
 * @brief 200. 岛屿数量
 * https://leetcode.cn/problems/number-of-islands/
 */
class UnionFind;

class Solution {
public:
    // DFS (Recommended)
    int numIslands(vector<vector<char>>& grid) {  // O(MN) O(MN)
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int res = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++res;
                    dfs(grid, r, c);
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();

        grid[r][c] = '0';  // 把访问过的重置为 0，避免重复访问 || 也可以置为 2
        if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
    }

    // BFS (a bit slow)
    int numIslandsBFS(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> visited(m, vector<int>(n, 0));
        int res = 0;
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    visited[i][j] = 1;
                    BFS(i, j, grid, visited);
                    res++;
                }
            }
        }
        return res;
    }

    void BFS(int x, int y, vector<vector<char>>& grid, vector<vector<int>>& visited) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        q.push({x, y});
        while (!q.empty()) {
            auto pos = q.front(); q.pop();
            int pos_x = get<0>(pos), pos_y = get<1>(pos);

            // 上下左右的搜索区域
            vector<int> is = {max(0, pos_x-1), min(m-1, pos_x+1)};
            vector<int> js = {max(0, pos_y-1), min(n-1, pos_y+1)};

            for (int i : is) {
                if (!visited[i][pos_y]) {
                    visited[i][pos_y] = 1;
                    if (grid[i][pos_y] == '1') q.push({i, pos_y});
                }
            }
            for (int j : js) {
                if (!visited[pos_x][j]) {
                    visited[pos_x][j] = 1;
                    if (grid[pos_x][j] == '1') q.push({pos_x, j});
                }
            }
        }
    }

    // // 并查集解法
    // // 如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。
    // // O(MN*alpha(MN))  O(MN)
    // int numIslandsUnionFind(vector<vector<char>>& grid) {
    //     int nr = grid.size();
    //     if (!nr) return 0;
    //     int nc = grid[0].size();
    //
    //     UnionFind uf(grid);
    //     int num_islands = 0;
    //     for (int r=0; r<nr; ++r) {
    //         for (int c=0; c<nc; ++c) {
    //             if (grid[r][c] == '1') {
    //                 grid[r][c] = '0';
    //                 if (r - 1 >= 0 && grid[r-1][c] == '1') uf.unite(r * nc + c, (r-1) * nc + c);
    //                 if (r + 1 < nr && grid[r+1][c] == '1') uf.unite(r * nc + c, (r+1) * nc + c);
    //                 if (c - 1 >= 0 && grid[r][c-1] == '1') uf.unite(r * nc + c, r * nc + c - 1);
    //                 if (c + 1 < nc && grid[r][c+1] == '1') uf.unite(r * nc + c, r * nc + c + 1);
    //             }
    //         }
    //     }
    //     return uf.getCount();
    // }
};


// class UnionFind {
// private:
//     int count;
//     vector<int> parent;
//     vector<int> rank;
// public:
//     explicit UnionFind(vector<vector<char>>& grid) {
//         count = 0;
//         int m = grid.size();
//         int n = grid[0].size();
//         for (int i=0; i<m; ++i) {
//             for (int j=0; j<n; ++j) {
//                 if (grid[i][j] == '1') {
//                     parent.push_back(i*n+j);
//                     ++count;
//                 } else {
//                     parent.push_back(-1);
//                 }
//                 rank.push_back(0);
//             }
//         }
//     }
//
//     int find(int i) {
//         return (parent[i] == i) ? parent[i] : (parent[i] = find(parent[i]));
//     }
//
//     int unite(int x, int y) {
//         int rootx = find(x);
//         int rooty = find(y);
//         if (rootx != rooty) {
//             if (rank[rootx] < rank[rooty]) {
//                 swap(rootx, rooty);
//             }
//             parent[rooty] = rootx;
//             if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
//             --count;
//         }
//     }
//
//     int getCount() const {
//         return count;
//     }
// };

int main() {
    vector<vector<char>> grid{{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};
    Solution sol;
    int res = sol.numIslands(grid);
    cout << res << endl;
    return 0;
}
